package com.code.leetcode._202505;

import java.util.ArrayList;
import java.util.List;

/**39. 组合总和 ，难度为 中等。***/
public class CombinationSum {
    /**给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合
     * candidates中的数字可以无限制重复被选取
     * 说明：所有数字都是正整数
     * 解集不能包含重复的组合
     * 示例1：输入：candidates=[2,3,6,7],target =7,
     * 所求解集为：[[7],[2,2,3]]
     * 示例2：输入：candidates=[2,3,5],target =8,
     * 所求解集为：[[2,2,2,2],[2,3,3],[3,5]]**/
    public List<List<Integer>>  combinationSum(int[] cs,int t){
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(cs,t,0,ans,cur);
        return ans;
    }
    /**cs是原数组，从该数组进行选数
     * t：还剩多少值需要凑成，起始值为target，代表还没选择任何数，当t=0代表选择的数凑成了targer
     * u：当前决策到cs[]中的第几位
     * ans：最终结果集
     * cur：当前结果集
     **/
    void dfs(int[] cs, int t,int u,List<List<Integer>> ans, List<Integer> cur){
        if (t == 0){
            ans.add(new ArrayList<>(cur));
            return;
        }
        if (u == cs.length || t < 0) return;
        //枚举cs[u]的使用次数
        for (int i = 0; cs[u] * i <= t; i++){
            dfs(cs,t-cs[u]*i, u+1,ans,cur);
            cur.add(cs[u]);
        }
        //进行回溯，注意回溯总是将数组的最后一位弹出
        for (int i = 0; cs[u]* i <= t; i++){
            cur.remove(cur.size()-1);
        }
    }


}
